package first.niuke.midding;

/**
 * @ClassName NC88
 * @description:
 * @author: 荣燊
 * @create: 2021-04-13 13:30
 **/
public class NC88 {
    // 寻找第K大

    public static void main(String[] args) {
        int[] t = {1332802,1177178,1514891,871248,753214,123866,
                1615405,328656,1540395,968891,1884022,252932,1034406,
                1455178,821713,486232,860175,1896237,852300,566715,
                1285209,1845742,883142,259266,520911,1844960,218188,
                1528217,332380,261485,1111670,16920,1249664,1199799,
                1959818,1546744,1904944,51047,1176397,190970,48715,
                349690,673887,1648782,1010556,1165786,937247,986578,798663};
        int n = t.length, k = 6;

        System.out.println(findKth(t, 49, 24));
    }

    public static int findKth(int[] a, int n, int K) {
        // write code here
        int[] res = quickSort(a, 0, n-1);
        return res[n-K];
    }

    public static int[] quickSort(int[] a, int left, int right) {
        if (left < right) {
            int posi = position(a, left, right);
            quickSort(a, left, posi-1);
            quickSort(a, posi+1, right);
        }
        return a;
    }

    public static int position(int[] a, int left, int right) {
        int i = left;
        int j = right;
        int temp = a[left];
        while (i < j) {
            while (i < j && a[j] >= temp) {
                j--;
            }
            swap(a, i, j);
            while (i < j && a[i] <= temp) {
                i++;
            }
            swap(a, i, j);

        }
        return i;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


}
